//
// Created by Administrator on 2021/4/12.
//

/*
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。


示例 1：

输入：nums = [10,2]
输出："210"
示例2：

输入：nums = [3,30,34,5,9]
输出："9534330"
示例 3：

输入：nums = [1]
输出："1"
示例 4：

输入：nums = [10]
输出："10"
 

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 109

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    string largestNumber(vector<int> &nums) {
        // 排序 按照第一位、第二位的次序
        // 先变成字符串
        vector<string> vs(nums.size());
        for (vector<int>::size_type i = 0; i < nums.size(); ++i) {
            vs[i] = to_string(nums[i]);
        }
        sort(vs.begin(), vs.end(), [](const string &a, const string &b) {
            return a + b > b + a;
        });
        if (vs[0] == "0") return "0";
        string ans;
        for (const auto &i :vs) {
            ans += i;
        }
        return ans;
    }

};


class Solution2 {
public:
    string largestNumber(vector<int> &nums) { // 题解
        sort(nums.begin(), nums.end(), [](const int &x, const int &y) {
            long sx = 10, sy = 10;
            while (sx <= x) {
                sx *= 10;
            }
            while (sy <= y) {
                sy *= 10;
            }
            // 构造出两个数连接后的值 比较大小
            return sy * x + y > sx * y + x;  // 从大到小排序
        });
        if (nums[0] == 0) { // 最大的是0 结果只能是0
            return "0";
        }
        string ret;
        for (auto &x : nums) {
            cout << x << endl;
            ret += to_string(x);
        }
        return ret;
    }
};

int main() {
    vector<int> v{3, 30, 34, 5, 9};
    Solution sol;
    cout << sol.largestNumber(v) << endl;
    return 0;
}
